package algocasts;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class P150_DiameterOfBinaryTree {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    private int maxDepth(TreeNode root, int[] d) {
        if (root == null) return 0;
        int left = maxDepth(root.left, d);
        int right = maxDepth(root.right, d);
        d[0] = Math.max(d[0], left + right);
        return Math.max(left, right) + 1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        int[] d = new int[1];
        maxDepth(root, d);
        return d[0];
    }
}
